void calcPi(char*T,int m) {
	int j=0;
	while(T[j]==T[j+1]) j++;
	pi[1]=j;
	int k=1;
	for(int i=2;i<m;i++) {
		int len=k+pi[k]-1,L=pi[i-k];
		if (L<len-i+1) pi[i]=L;
		else {
			j=max(len-i+1,0);
			while(T[j]==T[j+i]&&i+j<m) j++;
			pi[k=i]=j;
		}
	}
}
void ext_kmp(char*S,char*T,int n,int m,int*ext,int*pi) {
	calcPi(T,m);
	int j=0,k=0;
	while(S[j]==T[j]&&j<n&&j<m) j++;
	ext[0]=j;
	for(int i=1;i<n;i++) {
		int len=k+ext[k]-1,L=pi[i-k];
		if (L<len-i+1) ext[i]=L;
		else {
			j=max(len-i+1,0);
			while(S[i+j]==T[j]&&i+j<n&&j<m) j++;
			ext[k=i]=j;
		}
	}
}